<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>shellSort</title>
</head>

<body>
    <script>
        // shellSort
        function shellSort(arr) {
            for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
                // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
                for (let i = gap; i < arr.length; i++) {
                    let j = i - gap;
                    let temp = arr[i];
                    for (; j >= 0 && arr[j] > temp; j -= gap) {
                        arr[j + gap] = arr[j]
                    }
                    arr[j + gap] = temp;
                }
            }
            return arr;
        }

        // example
        console.log(shellSort([9, 55, 4, 1, -2, 8]))
    </script>
</body>

</html>